Content addressable memory (CAM) devices, sometimes also referred to as “associative memories”, can provide rapid matching functions between an applied data value (e.g., a comparand, compare data, or search key) and stored data values (e.g., entries). Such rapid matching functions are often utilized in routers, network switches, and the like, to process network packets. As but one particular example, a router can use a matching function to match a destination of an incoming packet with an entry in a “forwarding table” to thereby forward a packet toward its ultimate destination.
Among the numerous other applications for CAM devices are access control lists (ACLs) that can control access of a user to various portions of a file system, and translation lookaside buffers (TLBs) that can translate between “virtual” and “real” addresses in a computer system.
A typical CAM device can store a number of data values in a CAM cell array. In a compare (i.e., match) operation, entries can be compared to a compare data value. An entry that matches the compare data value can result in the generation of a match indication.
A typical CAM device can also include prioritization of match results. That is, if multiple entries match a given compare data value (multiple match case), one entry can be selected as a “winning” entry according to predetermined criteria. In many cases, an entry having the lowest address is selected as the winning entry in a multiple match case.
In many CAM devices, match indications for entries are provided by conductive match lines. Such match lines can be set to a predetermined voltage prior to a compare operation. Subsequently, when a compare operation takes place, the match line(s) corresponding to a mismatch (MISS) result can have a different voltage than a match line having match (HIT) result. Even more particularly, in one type of “miss-sensing” architecture, match lines can be precharged to a “HIT” voltage. In a subsequent compare operation, those match lines corresponding to MISS result can be discharged. Any match lines remaining at the HIT voltage can indicate a HIT result. Conversely, in one type of “hit-sensing” architecture, match lines can be predischarged to a “MISS” voltage, and those match lines corresponding to a HIT result can be charged to a different potential by the compare operation. In any event, as multiple match lines are charged and discharged, current (and hence power) is consumed by a CAM device.
In a conventional CAM device, search operations can be conducted in response to a system clock, with searches being undertaken every clock cycle. As a result, CAM devices can consume considerable power as match lines in the CAM cell array are continuously charged and discharged each clock cycle.
In light of the above, it would be desirable to arrive at some way of reducing the current drawn by a CAM device during search operations.
CAM devices operating in synchronism with a periodic external clock signal, as noted above, can be considered synchronous devices. However, a CAM device can also be an asynchronous CAM, performing matching functions on applied comparand values according to a non-periodic timing signal (such as an applied comparand value, as just one example).
CAM devices can include “binary” CAM devices in which a multi-bit compare data value must match with every bit of a stored data value to generate a match indication. CAM devices can also include “ternary” CAMs in which a multi-bit compare data value can be compared with “maskable” stored data values. As is well understood by those skilled in the art, a “maskable” data value has bits that can be masked from the compare operation. A masked bit will not generate a mismatch indication even if the masked data value bit is different than the corresponding compare value bit. Thus, a match indication can include a binary and/or a ternary match indication, according to the type of CAM device.
Another important feature of integrated circuit devices, such as CAM devices, can be a power supply transient current drawn by such a device. In particular, when a conventional CAM device is not in a search mode, the device may draw a reduced amount of current by not activating the CAM array. However, upon entering a search mode, the CAM device will draw a significant transient current. Transient currents that are undesirably high can be hard to accommodate in some system power supplies.
Accordingly, it would be desirable to arrive at some way of reducing transient currents drawn by a CAM device when switching from a non-search mode to a search mode.
A conventional CAM will now be described to better understand the various disclosed embodiments of the present invention.
Referring now to FIG. 15, one example of a conventional CAM is set forth in a block schematic diagram and designated by the general reference character 1500. A conventional CAM 1500 can include a CAM block 1502, compare data drivers 1504, match sense amplifiers (MSA0 to MSAn) 1506, and result registers (REG0 to REGn) 1508. A CAM block 1502 can include a number (n+1) of rows 1510-0 to 1510-n, each of which can include a number of CAM cells, one of which is shown as 1512. CAM cells 1512 of the same row can be commonly connected to a match line MATCH0 to MATCHn. Further, the CAM cells 1512 can also be arranged into a number of columns (Col 0 to Col 79).
A match (compare or search) operation can include a precharge phase and an evaluate phase. During the precharge phase match sense amplifiers 1506 and match lines (MATCH0 to MATCHn) can be precharged to a predetermined voltage prior to the search key being applied. During the evaluate phase, a search key, composed of COMPAREDATA[0:79], can applied to CAM block 1502. In particular, compare data drivers 1504 can apply the search key as complementary values to CAM block 1502. Complementary bit values CD O/BCD 0 to CD 79/BCD 79 can be applied to corresponding columns (COL 0 to COL 79) of CAM cells 1512.
It is noted that the search key COMPAREDATA[0:79] can be considered a “native” word width. A native word width can be the smallest supported word width of a CAM device. Thus, it is understood that in FIG. 15, a CAM device can include 80 compare data input pins. Multiples of the native word width may also be supported by the CAM device.
In the search operation, the compare data (CD0/BCD0 to CD79/BCD79) can be compared against values stored in the CAM cells 1512. If a mismatch occurs for any CAM cell 1512 of a given row (1510-0 to 1510-n), the corresponding match line (MATCH0 to MATCHn) can be discharged to another potential. Otherwise, a match line (MATCH0 to MATCHn) can remain at the precharged potential.
Match sense amplifiers 1506 can sense when a corresponding match line (MATCH0 to MATCHn) remains at a precharged potential, and provides an output that can be held in result registers 1508 to indicate a hit or miss. If more than one hit occurs, a priority encoder (not shown) can determine which hit indication is the “winning” indication (e.g., lowest address entry).
In the most common CAM applications, mismatch results predominate. That is, a typical search operation will generate few, if any match indications, with most rows registering mismatch indications.
From the above description, assuming the CAM 1500 executes a match indication every cycle, once per cycle, the entire CAM block 1502 will be precharged. Further, each match sense amplifier (MSA0 to MSAn) can be enabled, and all compare data drivers 1504 can be activated.
U.S. Pat. No. 6,240,000 issued to Sywyk et al. on May 29, 2001 (hereinafter the '000 patent), discloses a CAM device with a reduced transient current. In the embodiments of the '000 patent, one comparand value can be sequentially compared to different CAM blocks within different portions of a single clock cycle to reduce peak transient currents. In addition, the '000 patent shows embodiments that receive portions of a comparand as input values (native words), and combine search results from such portion to give an overall match result for a comparand larger than a received input value (search values larger than a native word size).
The '000 patent also describes using a mismatch indication from one compare operation to disable precharge and other aspects of a subsequent compare operation in the case of word widths greater than the native word width.